#include<bits/stdc++.h>
using namespace std;
long long C,T,n,m,x,cnt,u[1000010],v[1000010],h[2010],nxt[2000010],to[2000010],d[2010],f[2010][2010],sm,mx,ans;
queue<int>q;
void add(int u,int v){nxt[++cnt]=h[u],to[cnt]=v,h[u]=cnt;}
int main(){
	freopen("oi.in","r",stdin);
	freopen("oi.out","w",stdout);
	cin>>C>>T;
	while(T--){
		cin>>n>>m,mx=-1e9,ans=0;
		for(int i=1;i<=m;i++)cin>>u[i]>>v[i];
		if(n<=6){
			for(int ii=1;ii<(1<<(n*(n-1)/2));ii++){
				sm=0;
				for(int i=1,k=0;i<n;i++)for(int j=i+1;j<=n;j++,k++)f[i][j]=f[j][i]=(ii>>k&1)?1:1e9,sm+=ii>>k&1;
				if(sm!=m-1)continue;
				sm=0;
				for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
				for(int i=1;i<=m;i++)sm+=f[u[i]][v[i]];
				if(-sm>mx)mx=-sm,ans=1;
				else if(-sm==mx)ans++;
			}
			cout<<mx<<" "<<ans<<"\n";
		}else if(n==m)cout<<-n*2+2<<" "<<1<<"\n";
		else{
			cnt=0;
			for(int i=1;i<=n;i++)h[i]=d[i]=0;
			for(int i=2;i<=m;i++)add(u[i],v[i]),add(v[i],u[i]);
			q.push(u[1]);
			while(!q.empty()){
				x=q.front(),q.pop();
				for(int i=h[x];i;i=nxt[i])if(!d[to[i]]&&to[i]!=u[1])d[to[i]]=d[x]+1,q.push(to[i]);
			}
			cout<<-m+1-d[v[1]]<<" "<<1<<"\n";
		}
	}
	return 0;
}
